package toOffer;

/**
 * <h3>leetcode</h3>
 *
 * @author BigFaceCat
 * @date 2024/2/27 18:27
 * @description <p>每日温度</p>
 */

import java.util.*;

/**
 * 题目：输入一个数组，它的每个数字是某天的温度。请计算每天需要
 * 等几天才会出现更高的温度。例如，如果输入数组[35, 31, 33, 36, 34]，那么
 * 输出为[3, 1, 1, 0, 0]。由于第 1 天的温度是 35℃，要等 3 天才会出现更高的
 * 温度 36℃，因此对应的输出为 3。第 4 天的温度是 36℃，后面没有更高的
 * 温度，它对应的输出是 0。其他的以此类推。
 */
public class toOffer6_2_38 {
    public static void main(String[] args) {
        int[] temperatures = {30,60,90};
        int[] list = dailyTemperatures(temperatures);
        for (int e : list) {
            System.out.print(e + " ");
        }
    }

    /**
     * 思想：
     * （1）栈为空，数据直接入栈；
     * （2）栈不为空，判断当前要入栈的新数据newElement与栈顶数据的大小：
     * 如果栈顶的数据大那就newElement直接进栈；如果newElement大那就栈顶元素出栈，直到栈为空或者栈顶元素比newElement大
     *
     * @param temperatures
     * @return
     */
    public static int[] dailyTemperatures(int[] temperatures) {
        LinkedList<Integer> stack = new LinkedList<>();
        int[] arr = new int[temperatures.length];

        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]){
                arr[stack.peek()] = i - stack.peek();
                stack.pop();
            }
            stack.push(i);
        }

        return arr;
    }
}